package com.utils;

public class MyLinkList {

    //使用内部类定义数据结点
    //封装
    private static class Node{
        Map data;
        Node next;

        public Node(Map data) {
            this.data = data;
            this.next=null;
        }

        public Map getData() {
            return data;
        }

        public void setData(Map data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }


    }
    //存放头结点、尾结点、数组长度
    private Node head;
    private Node last;
    private int size;

    public int getSize(){
        return size;
    }

    /**
     * 向头部添加结点
     * @param ele
     */
    public void addHead(Map ele){
        Node newHead = new Node(ele);
        if (size == 0)
            last = newHead;
        if (head != null){
            newHead.setNext(head);
        }
        head = newHead;
        size++;
    }

    /**
     * 向尾部添加结点
     * @param ele
     */
    public void addLast(Map ele){
        Node newLast = new Node(ele);
        if (size == 0)
            head = newLast;
        if (last != null){
            last.setNext(newLast);
        }
        last = newLast;
        size++;
    }

    /**
     * 根据索引位置插入元素
     * @param ele 元素
     * @param index 索引位置
     */
    public void inserEle(Map ele, int index) {

        //判断插入索引位置，
        // 1、是否超出集合范围。
        // 2、插入位置为前、中、末

        //判断索引插入是否超出范围
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("超出集合范围");
        if (size == 0) {
            Node node = new Node(ele);
            head = node;
            last = node;
            size++;
            return;
        }
        if (index == 0) {
            addHead(ele);
            return;
        }
        //索引在0到size
        if (index > 0 && index < size) {
            Node node = new Node(ele);
            Node pre = null;
            Node temp = head;
            int i = 0;
            while (temp != null) {
                if (index-1 == i) {
                    pre = temp;
                    break;
                }
                temp = temp.next;
                i++;
            }
            Node next=pre.next;
            pre.setNext(node);
            node.setNext(next);
            size++;
            return;
        }
        if (index == size) {
            addLast(ele);
        }
    }


    /**
     * 获取头元素
     * @return ele
     */
    public Node getFirst(){
        if(size==0)
            throw new IndexOutOfBoundsException("超出数组范围");
        return this.head;
    }

    /**
     * 获取尾元素
     * @return ele
     */
    public Node getLast(){
        if(size==0)
            throw new IndexOutOfBoundsException("超出数组范围");
        return this.last;
    }



    /**
     * 获取指定索引的元素
     * @param index 索引
     * @return ele 元素
     */
    public Node get(int index){
        if(index<0||index>=size)
            throw new IndexOutOfBoundsException("超出数组范围");
        Node temp=head;
        for (int i = 0; i <=index ; i++) {
            temp=temp.next;
        }
        return  temp;
    }

    /**
     * 获取指定索引的元素的Map
     * @param index 索引
     * @return ele 元素
     */
    public Map getMap(int index){
        if(index<0||index>=size)
            throw new IndexOutOfBoundsException("超出数组范围");
        Node temp=head;
        for (int i = 0; i <=index ; i++) {
            temp=temp.next;
        }
        return  temp.data;
    }

    /**
     * 根据索引修改节点数据
     * @param index 索引
     * @param ele 数据
     * @return
     */
    public Node updateByIndex(int index,Map ele){
        if(index<0||index >= size)
            throw new IndexOutOfBoundsException("超出数组范围");
        Node temp=head;
        for (int i = 0; i <=index ; i++) {
            temp=temp.next;
        }
        temp.data = ele;
        return temp;
    }

    /**
     * 根据索引修改节点数据的Map
     * @param index 索引
     * @param ele 数据
     * @return
     */
    public Map updateBackMap(int index,Map ele){
        if(index<0||index>=size)
            throw new IndexOutOfBoundsException("超出数组范围");
        Node temp=head;
        for (int i = 0; i <=index ; i++) {
            temp=temp.next;
        }
        temp.data = ele;
        return temp.data;
    }

    /**
     * 删除指定索引的节点
     * @param index 索引
     * @return 要删除的节点
     */
    public Node delete(int index){
        if(index<0 || index>size)
            throw new IndexOutOfBoundsException("超出集合范围！");
        Node delNode=null;
        if(index==0){
            //删除头节点
            delNode=head;
            head=head.next;
        }else if(index==size-1){
            //删除尾节点
            //找到index前一个节点
            Node preNode=get(index-1);
            //找到要删除的节点
            delNode=preNode.next;
            //将上一个节点的下一个节点设置为null
            preNode.next=null;
            last=preNode;
        }else {
            //删除中间节点
            //找到要删除节点的上一个节点
            Node preNode=get(index-1);
            //找到要删除节点的下一个节点
            Node next=preNode.next.next;
            //找到要删除的节点
            delNode=preNode.next;
            //将要删除元素的上一个节点和下一个节点连接起来
            preNode.next=next;
        }
        size--;
        return delNode;
    }

    /**
     * 根据元素查找索引
     * @param ele
     * @return 索引
     */
    public int indexOf(Map ele){
        Node temp=head;
        for (int i = 0; i <size ; i++) {
            if(temp.getData() == ele){
                return i;
            }
            temp=temp.next;
        }
        return -1;
    }

    /**
     * 根据ID查找位置
     *
     * @param ID 道路ID号
     * @return 位置
     */
    public int indexOf_ID(int ID) {
        int i = -1;
        Node temp = head;
        while (temp != null) {
            i++;
            Map map = (Map) temp.getData();
            if (map.getLinkID() == ID) {
                return i;
            }
            temp = temp.next;
        }
        return -1;
    }

    /**
     * 对LinkID冒泡排序(优化)
     */
    public void bubbleSortOfID() {
        Node temp = head;
        Node pre = head;
        boolean flag = false;
        for (int i = 0; i < size; i++) {
            temp = head;
            for (int j = 0; j < size - i - 1; j++) {
                pre = temp;
                temp = temp.next;
                Map map1 = (Map) pre.getData();
                Map map2 = (Map) temp.getData();
                if (map1.getLinkID() > map2.getLinkID()) {
                    temp.data = map1;
                    pre.data = map2;
                    flag = true;
                }
            }
            if (!flag) break;
        }

    }

    /**
     * 对ID选择排序
     */
    public void selectSort(){
        Node p = head;
        Node q = head;
        Node small = head;
        while (q!=null){
            small=q;
            p=q;
            while (p.next!=null){
                p = p .next;
                Map map1 = (Map) small.getData();
                Map map2 = (Map) p.getData();
                if(map1.getLinkID()>map2.getLinkID()){
                    p.data=map1;
                    small.data=map2;
                }
            }q=q.next;
        }
    }


    /**
     * 快速排序入口
     */
    public void quickSort(){
        quickSort(head,last);
    }


    private Node quickSort(Node begin, Node end) {
        //判断为空，判断是不是只有一个节点
        if (begin == null || end == null || begin == end)
            return begin;
        //从第一个节点和第一个节点的后面一个几点
        //begin指向的是当前遍历到的最后一个<= nMidValue的节点
        Node first = begin;
        Node second = begin.next;

        Map nMidValue = begin.data;
        //结束条件，second到最后了
        while (second != end.next && second != null) {//结束条件
            //一直往后寻找<=nMidValue的节点，然后与fir的后继节点交换
            if (second.data.getLinkID() < nMidValue.getLinkID()) {
                first = first.next;
                //判断一下，避免后面的数比第一个数小，不用换的局面
                if (first.data.getLinkID() != second.data.getLinkID()) {
                    Map temp = first.data;
                    first.data = second.data;
                    second.data = temp;
                }
            }
            second = second.next;
        }
        //判断，有些情况是不用换的，提升性能
        if (begin != first) {
            Map temp = begin.data;
            begin.data = first.data;
            first.data = temp;
        }
        //前部分递归
        quickSort(begin, first);
        //后部分递归
        quickSort(first.next, end);
        return begin;

    }

    /**
     * 链表的插入排序
     */
    public void insertionSortList(){

        Node pre = head;//pre指向已经有序的节点
        Node cur = head.next;//cur指向待排序的节点

        Map temp = null;
        Node aux = new Node(temp);//辅助节点
        aux.next = head;

        while(cur!=null){
            if(cur.data.getLinkID() < pre.data.getLinkID()){
                //先把cur节点从当前链表中删除，然后再把cur节点插入到合适位置
                pre.next = cur.next;

                //从前往后找到l2.data.getLinkID>cur.data.getLinkID,然后把cur节点插入到l1和l2之间
                Node l1 = aux;
                Node l2 = aux.next;
                while(cur.data.getLinkID() > l2.data.getLinkID()){
                    l1 = l2;
                    l2 = l2.next;
                }
                //把cur节点插入到l1和l2之间
                l1.next = cur;
                cur.next = l2;//插入合适位置

                cur = pre.next;//指向下一个待处理节点

            }else{
                pre = cur;
                cur = cur.next;
            }
        }
    }

    /**
     * 归并排序入口方法
     */
    public void mergeSortList(){
        mergeSortList(head);
    }

    /**
     * 归并排序
     * @return
     */
    private Node mergeSortList( Node head01 ){
        if(head01 == null || head01.next==null)    return head01;
        Node mid = getMid(head01);//获取链表中间节点

        //把链表从之间拆分为两个链表：head和second两个子链表
        Node second = mid.next;
        mid.next = null;
        //对两个子链表排序
        Node left = mergeSortList(head01);
        Node right = mergeSortList(second);

        return merge(right,left);
    }


    //两个有序链表的归并
    private Node merge(Node l1,Node l2){
        //辅助节点，排好序的节点将会链接到dummy后面
        Map temp = null;
        Node dummy = new Node(temp);

        Node tail = dummy;//tail指向最后一个排好序的节点
        while(l1 != null  && l2 != null){
            if(l1.data.getLinkID() <= l2.data.getLinkID()){
                tail.next = l1;
                l1 = l1.next;
            }else{
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next; //移动tail指针
        }

        if(l1 != null)
            tail.next = l1;
        else
            tail.next = l2;

        return dummy.next;

    }

    //返回链表之间节点
    private Node getMid(Node head01){
        if(head01 ==null ||head01.next==null)    return head01;

        Node slow = head01;
        Node faster = head01.next;
        while(faster!=null&&faster.next!=null){
            slow = slow.next;
            faster = faster.next.next;
        }
        return slow;
    }





    @Override
    public String toString() {
        Node temp = head;
        while (temp != null){
            System.out.println(temp.data.toString());
            temp=temp.next;
        }
        return null;
    }













}
